1. Field of the Invention
The present invention relates to the operation of a communication bus in a multiprocessor computer system and, more specifically, to a bus protocol accessing interleaved memory modules.
2. Description of the Related Art
Due to the demand for increased processing speed and volume, many computer systems, and other information processing systems, employ multiple central processing units (CPUs). Typically, in such multiprocessor systems, multiple CPUs communicate with memory modules, input/output (I/O) devices, and other peripheral units, via a main system bus. Since the bus can only be used by one processor at a time, such multiprocessor systems typically use a bus protocol that determines which processors have control of the bus at any given time.
Within a typical multiprocessor system, the bus protocol calls for the bus to be in one of four phases, or states. In an inactive, or bus free state, none of the CPUs control the bus or are vying for control of the bus. The bus enters an arbitration state when one or more of the CPUs indicates that one of the memory modules, or other units accessible on the bus, is to be accessed. In the arbitration state, the CPUs competing for control of the system bus determine which CPU should gain control of the bus based upon the priority of the requests issued by the respective CPUs. Control of the bus is granted to one of the CPUs in a selection state. Once control of the bus has been granted to one of the CPUs, the bus enters an active, or data/control state wherein data and control signals are transferred over the bus to other units in communication with the bus.
Data bus width and clock speed are the bus parameters which are usually considered when measuring bus performance. However, in order to increase processing speed and volume, bus efficiency must be considered in addition to these parameters. That is, when a CPU has control of the bus, there is often some dead time wherein no data is being transferred along the bus. The efficiency of the bus decreases when dead time as a percentage of the time the CPU has control of the bus increases.
One of the main causes of bus inefficiency is the delay observed when a memory module has to recover data for successive CPU requests. When a first request is issued to a memory module, the module is generally in a ready state so that the memory module can access data with little delay (usually within one clock cycle). However, if the same memory module is immediately accessed again, the module typically will exhibit a delay before transferring data. This delay is typically called "recovery time." While the memory module is accessing data, no data is transferred across the system bus during the recovery time period. Thus, bus efficiency is decreased whenever successive requests are made to the same memory module.
One way to improve bus efficiency involves interleaving the memory addresses within the memory modules on a system bus. When memory modules are interleaved, successive memory storage locations (i.e., memory locations having consecutive addresses) are placed in separate memory modules. Since associated data is typically stored in successive memory storage locations, and a group of associated data is likely to be accessed at once, it is likely that a CPU will access several successive memory locations in a row for a typical memory access. By placing successive memory locations in separate memory modules, the effects of recovery time delay for a given memory module are reduced. This is because a CPU will typically request data from one memory module, and then request the next address, which is stored in another memory module, and so on, so that each memory module is given a chance to recover from the last request. Thus, interleaving memory modules has been found to be an effective way of increasing bus efficiency.
In multiprocessor systems, however, memory interleaving is typically not as effective. This is because the system bus must share multiple CPUs, and each CPU has an opportunity to vie for control of the system bus after each data transaction. That is, the system bus usually enters the arbitration state whenever more than one CPU has a request to fill. In a typical case, a first CPU may access successive memory locations (and hence, different memory modules) if it maintains control of the system bus, however, when a second CPU is granted control of the bus, the data requested by the second CPU will usually have no relation to the data requests of the first CPU. Thus, there is no way of assuring that a different memory module than the memory module just accessed by the first CPU will be accessed by the second CPU. This may result in bus inefficiency due to the recovery time when the same memory module is accessed by the second CPU. In this way, the benefits of memory interleaving may be severely compromised.
Some systems have attempted to compensate for the bus inefficiency associated with multiprocessor systems. For example, U.S. Pat. No. 4,669,056 entitled DATA PROCESSING SYSTEM WITH A PLURALITY OF PROCESSORS ACCESSING A COMMON BUS TO INTERLEAVED MEMORY STORAGE, to Waldecker, discloses a method of increasing system bus efficiency. In the Waldecker patent, the addresses accessed by each of the CPUs are selected so that when control of the bus is switched to another CPU, a memory request is assured of going to a different memory module than that accessed by the previous CPU. However, this method will not operate in conjunction with a conventional CPU (e.g., an INTEL CPU). Even if such a device were to be implemented within a CPU having pipelining capabilities, it appears that additional data buffer circuitry would be required to accommodate address requests which were not in the proper order to assure proper interleaving.
In another system, disclosed in U.S. Pat. No. 5,287,477 entitled MEMORY-RESOURCE-DRIVEN ARBITRATION, to Johnson, et al., special memory status queues hold information regarding the status of each of the interleaved memory modules in communication with the system bus. The master devices on the system bus (e.g., the CPUs) monitor the local memory status queue in order to determine which of the memory modules are busy. Those master devices which have pending requests for busy memory modules are inhibited from arbitrating for control of the system bus. However, such an implementation requires that master devices having requests to ready memory modules rearbitrate for control of the bus. This may cause system bus inefficiencies since the arbitration and selection states of the bus must be re-entered, and in these states no data or control signals are transferred over the system bus. Furthermore special queues are necessary to implement such a system.